﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.DataStructures.Digraphs;
using Algoritmia.DataStructures.Sets;
using Algoritmia.Utils;
using Lists = Algoritmia.DataStructures.Lists;

namespace Algoritmia.Problems.GraphColorer
{
	public class GraphColorer<T>
	{
	    private readonly Func<IEnumerable<T>, DataStructures.Sets.ISet<T>> _createSet;
	    private readonly Func<IEnumerable<T>, Lists.IList<DataStructures.Sets.ISet<T>>> _createList;

	    public GraphColorer(Func<IEnumerable<T>,DataStructures.Sets.ISet<T>> createSet = null,
                            Func<IEnumerable<T>,Lists.IList<DataStructures.Sets.ISet<T>>> createList = null)
        {
            _createSet = createSet ?? (it => AlgoritmiaFactory.Sets<T>.Default);
	        _createList = createList ?? (it => AlgoritmiaFactory.Lists<DataStructures.Sets.ISet<T>>.Default);
        }

        public IEnumerable<DataStructures.Sets.ISet<T>> Colors(IDigraph<T> g)
        {
            var vertices = _createSet(g.V);
            foreach(var v in g.V)
            {
                vertices.Add(v);
            }
            var partition = _createList(g.V);
            while ( vertices.Count > 0)
            {
                var lastColor = _createSet(g.V);
                foreach (var v in vertices.Where(v => lastColor.All(e => !g.Successors(e).Contains(v))))
                {
                    lastColor.Add(v);
                }
                partition.Add(lastColor);
                vertices = vertices.Substraction(lastColor);
            }
            return partition;
        }
 
	}
}
